// 基本思想：设定左右节点为数组两端，取两个节点中心位置mid，比较该值为target的大小，如果相等则返回中心位置
// 如果nums[mid] < target,则将左节点设置为mid+1，然后继续在右区间搜索
// 如果nums[mid] > target，则将右节点设置为mid - 1，然后继续在左区间搜索

// 时间复杂度：O(logn)
// 空间复杂度：O(1)
// 左闭右闭
function search(nums, target) {
    let left = 0
    let right = nums.length - 1
    while (left <= right) {
        let mid = Math.floor((right - left) / 2) + left
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] < target) {
            left = mid + 1
        } else {
            right =mid - 1 
        }
    }
    return -1
}

let arr = [1, 3, 4, 7, 8, 9]
console.log(search(arr, 7))

// 左闭右开
function search2(nums, target) {
    let left = 0
    let right = nums.length
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] < target) {
            left = mid + 1
        } else {
            right =mid
        }
    }
    return -1
}
console.log(search2(arr, 7))